home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 3148 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.8 KB  |  101 lines
  1. Newsgroups: comp.lang.c
  2. Path: in1.uu.net!world!mv!usenet
  3. From: ENGR@GSSI.MV.COM (Michael Furman)
  4. Subject: Re: Fastest way to computer log(base2) of x?
  5. Message-ID: <DLsnt4.48s@mv.mv.com>
  6. Mime-Version: 1.0
  7. Organization: GSSI
  8. Date: Fri, 26 Jan 1996 15:17:27 GMT
  9. References: <4e61iu$p6e@villa.fc.net>
  10. X-Newsreader: WinVN 0.93.10
  11. X-Nntp-Posting-Host: gssi.mv.com
  12.  
  13. In article <4e61iu$p6e@villa.fc.net>, avinash@paranoia.com says...
  14. >
  15. >[And no, this is not for a homework exercise.]
  16. >[BTW, the non-abridged C FAW at http://www.eskimo.com/~scs/C-faq.top.html
  17. >does not seem to be accessible??]
  18. >
  19. >I am trying to find out what could be the fastest way to compute
  20. >the position of the highest bit in any given integer -- basically, the
  21. >logarithm to the base 2 of any number.
  22. >
  23. >Simplistically, one could do :
  24. >logbase2(int x)
  25. >{
  26. >    if (IS_SET_BIT_31(x)) return 31;
  27. >    if (IS_SET_BIT_30(x)) return 30;
  28. >    etc.
  29. >}
  30. >
  31. >An improvement would be to check for BITS_31_16 and BITS_15_0 at first, and
  32. >then check for BITS_31_24, and BITS_23_16, etc .. (divide problem in half
  33. >at each stage).
  34. >
  35. >Any thoughts or other ideas?
  36.  
  37. If you know that it is power of 2 - you can just use '1' bits counting
  38. algorithm for x-1:
  39.  
  40. int bitcnt(unsigned long x) // calculates number of 
  41. '1' bits in word
  42.   {
  43.   unsigned long w;
  44.   w = (x & 0x55555555l) + ((x >> 1) & 0x55555555l);
  45.   w = (w & 0x33333333l) + ((w >> 2) & 0x33333333l);
  46.   w = w + (w >> 4);
  47.   w = (w & 0x000F000F) + ((w >> 8) & 0x000F000F);
  48.   return (int)((w + (w >> 16)) & 0xFF);
  49.   }
  50.  
  51. int log2(unsigned long x)    
  52.   {
  53.   assert(x != 0);
  54.   return bitcnt(x - 1);
  55.   }  
  56.  
  57. If not - you can make all lower bits "1" by the following code:
  58.  
  59.     x |= x >> 1;
  60.     x |= x >> 2;
  61.     x |= x >> 4;
  62.     x |= x >> 8;
  63.     x |= x >> 16;
  64.  
  65. But it is "theoretical" solution (using o(log(n)) time where n is number of 
  66. bits in word. In reality I would rather reccomend two methods:
  67.  
  68. 1. Using special CPU command. Intel 386+ hav one.
  69. 2. Using directly indexed table (al least for byte - 256 byte size). And 
  70. check four bytes one by one:
  71.  
  72.     result = tab[(x >> 24) & 0xFF]; 
  73.     if(result != 0)
  74.       return result - 1 + 24;
  75.  
  76.     result = tab[(x >> 16) & 0xFF]; 
  77.     if(result != 0)
  78.       return result - 1 + 16;
  79.     ............
  80.  
  81. Note: all code are just samples and are not tested. But I used these 
  82. algorithms a number of times - they works.
  83. >
  84. >Thanks!
  85. >
  86. >-- 
  87. >----
  88. >Avinash Chopde
  89. >e-mail: avinash@acm.org
  90. >home page: http://www.paranoia.com/~avinash/
  91.  
  92. -- 
  93. <<<<<<<< This is a copy of post to the newsgroup >>>>>>>>
  94. ---------------------------------------------------------------
  95. Michael Furman,                       (603)893-1109
  96. Geophysical Survey Systems, Inc.  fax:(603)889-3984
  97. 13 Klein Drive - P.O. Box 97          engr@gssi.mv.com 
  98. North Salem, NH 03073-0097            71543.1334@compuserve.com
  99. ---------------------------------------------------------------
  100.  
  101.